package q40_combinationSum2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution_2 {

    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, 0, 0);
        return res;
    }

    private void dfs(int[] candidates, int target, int sum, int beginIndex) {
        // 其实这个判断可以去除 因为在for循环里已经加入了判断条件
        if (sum > target){
            return;
        }

        if (sum == target){
            res.add(new ArrayList<>(path));
        }

        for (int i = beginIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            // 这个判断的意思是 如果i已经不是起始节点，并且此时数组中i位置和i - 1位置的数字一样 那么应该跳过
            // 我们举例说明：
            // 如果我们有 1 2 2 3一组数
            // 首先第一个循环会选取1 然后进入dfs 此时会从i + 1 位置开始选择数， 也就是2 2 3 假设我们需要target为3
            // 此时如果不判断，那么会在第二个dfs中选择2两次 也就是有了两个一样的结果
            if (i != beginIndex && candidates[i] == candidates[i - 1]){
                continue;
            }
            path.add(candidates[i]);
            sum += candidates[i];
            dfs(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}
